//https://blog.csdn.net/m0_58086930/article/details/120340921
// comments：good

#include <algorithm>
#include <climits>
#include <queue>
#include <vector>
#include <stack> 
#include <limits>

using namespace std;
struct Node {
	int val;
	struct Node *left;
	struct Node *right;
	Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

class ReturnInfo {
public:
	int height;
	int no;//结点个数
	ReturnInfo(int h, int n) {
		height = h;
		no = n;
	}
};
bool isFBT(Node* head) {
	ReturnInfo info = process2(head);
	return info.no == (1 << info.height - 1);//左移h位相当于2的h次方
}
ReturnInfo process2(Node* head) {
	if (head == NULL)
		return ReturnInfo(0, 0);
	ReturnInfo leftInfo = process2(head->left);
	ReturnInfo rightInfo = process2(head->right);
	return ReturnInfo(max(leftInfo.height, rightInfo.height) + 1, leftInfo.no + rightInfo.no + 1);
}